package 力扣_算法题综合.自己不会但觉得高频;

import java.util.*;

/**
 * @author zx
 * @create 2023-01-08 21:43
 */
public class 三数之和_15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//数组排序
        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {//固定第一个数，转化为求两数之和
            if (nums[i] > 0) {
                //第一个数大于0，后面的数都比它大，肯定不成立了
                return res;
            }
            int second = i + 1;
            int third = nums.length - 1;
            int sum = 0;
            // 双指针在nums[i]后面的区间中寻找和为0-nums[i]的另外两个数(second和third)
            while (second < third) {
                sum = nums[i] + nums[second] + nums[third];
                if(sum < 0){
                    second++;
                }else if(sum > 0){
                    third--;
                }else if(sum == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    //去重：第二个数和第三个数也不重复选取
                    if (!set.contains(list)) {
                        res.add(list);
                        set.add(list);
                    }
                    third--;
                }
            }
        }
        return res;
    }
}
